1. Field of the Invention
The present invention is directed to a system for recalculating a path in a network.
2. Description of the Related Art
Computers have revolutionized the idea of modeling systems for enhanced study and use of the systems. One example is the modeling of a system as a network. A network is defined in its most general sense as something that includes a number of paths that interconnect or branch out. Many systems that involve decisions can be modeled as a network. For example, a manufacturing process or a system of providing medical treatment can be modeled as a network of decision points and actions between decision points. A network can be represented in electronic form and stored on a processor readable storage medium so that software can be created for using the network model to study or use the system.
One example of a useful network that can be stored in electronic form is an electronic map, which includes geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited; for example, electronic maps could include distances between elements, travel time, lot numbers, tax information, tourist information, processing time, waiting time, etc. Additionally, storing a map as an electronic file allows for unlimited software applications to manipulate that data.
One advantage of the electronic map is that it can store and determine costs associated with various portions of a map. A cost is a variable that can be minimized or maximized. Note that the costs are not necessarily monetary costs. Examples of costs include time, distance, tolls paid, ease of turning, quality of scenery, etc. A more detailed discussion of costs can be found in U.S. patent application Ser. No. 08/756,263, Using Multiple Levels Of Costs For A Pathfinding Computation, filed Nov. 25, 1996, Richard F. Poppen, and U.S. patent application Ser. No. 08/581,169, Cost Zones, filed Dec. 29, 1995, Richard F. Poppen, both of which are incorporated herein by reference. Typically costs are represented as integers; however, costs can be represented as real numbers.
Electronic maps, as well as other networks, can be used for pathfinding, which is a method for computing a route between an origin and a destination in the network. Some systems compute recommended routes and guide (or report to) the driver by highlighting the recommended route on a map display, or by giving turn-by-turn directions, or other suitable guidance means.
When a pathfinding system is computing a recommended route to a destination, it does so by finding the most desirable route according to certain specified criteria. These criteria may be specified by the driver, or may be set as defaults at the time of manufacture. Often, a system will be used to find a path that minimizes (or maximizes) some cost, for example, driving time. A more detailed discussion of pathfinding is found in U.S. patent application Ser. No. 08/802,733, "Caching For Pathfinding Computation," filed Feb. 20, 1997, Richard F. Poppen, et al. and U.S. patent application Ser. No. 08/756,258, "Method For Determining Exits and Entrances For A Region In A Network," Filed Nov. 25, 1996, Richard F. Poppen, both of which are incorporated herein by reference.
An electronic map that is used for pathfinding must carry information about the connectivity of a road network, that is, information about the ways in which pieces of road do or do not connect to each other, for example, where there are ordinary intersections, where there are overpasses, where turns are restricted, and so on. For an area of any significant extent, this is a very large amount of information. An electronic map can include tens or hundreds of megabytes of data. In order to hold such vast quantities of data economically and allow a user to replace maps with updated copie's easily, many current pathfinding system (which includes general purpose computers with pathfinding software, automotive navigation systems or other map application equipment) use CD-ROMs to store the electronic map data.
Although CD-ROMs hold a great deal of data, accessing that data can be relatively slow. For example, a typical CD-ROM drive used for automotive pathfinding may take on the order of 1/3 of a second for each read access. If a pathfinding system had to wait 1/3 of a second every time it needed data, the time needed to compute a path would not be acceptable to a user. A user of a navigational pathfinding system stored in a car typically demands very fast response times when requesting a path because a user currently driving in the car needs to know which way to turn. For these reasons, it is very important to minimize the number of disk accesses required to compute a path. It is noted that some systems may use peripheral devices other than CD-ROMs, for example, hard disks, floppy disks, solid state memory, etc. These other storage devices suffer similar access time limitations.
One attempt to minimize the number of disk accesses required to compute a path includes grouping map data into clusters, that is, grouping together on a CD-ROM (or other storage device) information about sets of road segments often used in the same path computation. For example, a number of consecutive segments of the same street, road segments that cross each other or road segments that lead to a highway may be stored in a single cluster. Note that these clusters need not be geographically based. Information about roads on two sides of a river in an area that is not close to a bridge would probably not be stored in the same cluster since the roads would not be used in relation to each other during path calculation even though they may be quite close to each other geographically. Information about highways over a wide area are good candidates to be stored together in one cluster because a path computation typically explores the connections of highways with other highways. There are many ways to cluster data to increase performance. One example of clustering data can be found in U.S. patent application Ser. No. 08/245,690, Method for Clustering Multi-Dimensional Data, filed May 18, 1994, Poppen et al., incorporated herein by reference. When clustering is used with a suitable cache methodology, the time for pathfinding is saved because information needed by the pathfinding computation is often already in the cache (or main memory) having been read as part of a cluster which includes data already used.
Caching is a well-known process of saving records recently read in order to reduce the number of disk/memory accesses. One of the most well known forms of caching includes using a small memory local to a processor called a cache memory. Certain data recently used is typically stored in the cache memory, with access to the cache memory being quicker than access to main memory. In this example, the cache memory caches data between main memory and a processor.
Another example of caching is to cache data between a storage device and main memory. An alternative to using a cache memory separate from main memory is to use a portion of main memory as the cache memory. When data is read from the storage device it is typically kept in the cache memory portion (hereinafter called "cache") of the main memory for a certain amount of time so that later access to that data will be quicker than accessing the storage device. The portion of the memory allocated as the cache will hold a number of records of data along with an indication of how recently each record has been used. When the program needs to read a given record, the program first looks in the cache for the record. If the record is in the cache, the program uses the information stored in the cache rather than reading the disk file again. If the record is not in the cache, and there is enough unused space in the cache to hold the record, the record is read into the cache and then used by the program. If the record is not in the cache and there is not enough unused space in the cache to hold the record, the least recently used record or records are discarded to provide sufficient room to hold the new record. A record of data could include one or more clusters of data or another suitable arrangement of data. If map data is clustered in such a way that information regarding a given road segment is often used shortly after the use of information regarding another road segment in the same cluster there will be a significant speed improvement in the pathfinding process because the number of accesses to the CD-ROM will be decreased.
Even with the improvements discussed above, path calculation can be a relatively lengthy process and the users of a pathfinding system generally do not want to wait very long for a path to be calculated.
Furthermore, it is not uncommon for a user to deviate from a planned route or path that was determined by a pathfinding system. The deviation may be made by mistake (e.g. forgetting to make a turn), deliberately (e.g. avoiding a traffic jam) or by necessity (e.g. a turn or way is temporarily forbidden due to construction). When a user of a pathfinding system deviates from a prior computed path, the user is likely to want the pathfinding system to compute a new recommended route from the user's new location to the original destination (called recalculating the path). At such times, the user typically has less patience than usual for a slow pathfinding computation. For example, the initial pathfinding calculation may have been performed while a driver is getting ready to start a trip, but the path re-calculation takes place while the driver is moving, and, possibly, disoriented or stressed.
Therefore, a system is needed that reduces the amount of time needed to re-calculate a path in a network when the user has deviated from a prior computed path.